package com.lsa.skienna.challenge.chap8;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class MyStupidQueens {
	
	private static final String LINE_SEPARATOR = System.getProperty("line.separator");
	
//	private static Collection<PartialSolution> fullSolutions = new HashSet<PartialSolution>();
	private static Collection<PartialSolution> fullSolutions = new ArrayList<PartialSolution>();

	public static void main(String[] args) {
		PartialSolution s = PartialSolution.createEmpty(8);
		backtrack(s);
	}
	
	private static void backtrack(PartialSolution s) {
		if (s.isFullSolution() /*&& !fullSolutions.contains(s)*/) {
			System.out.println(fullSolutions.size() + 1 + ":");
			fullSolutions.add(s);
			System.out.println(s.toString());
		}
		else {
			List<PartialSolution> partialSolutions = construct(s);
			for (PartialSolution partialSolution : partialSolutions) {
				if (!partialSolution.isDeadEnd()) {
					backtrack(partialSolution);
				}
				else{
//					System.out.println("Dead end detected:");
//					System.out.println(partialSolution.toStringImpl(true));
				}
			}
		}
	}
	
	private static List<PartialSolution> construct(PartialSolution s) {
		List<PartialSolution> solutions = new ArrayList<PartialSolution>();
		
		CellState[][] desk = s.getDesk();
		for (int i = 0; i < desk.length; i++) {
			for (int j = s.getMaxCol() + 1; j < desk[i].length; j++) {
				if (desk[i][j] == CellState.FREE) {
					PartialSolution newPartialSolution = s.clone();
					newPartialSolution.putQueenAt(i, j);
					solutions.add(newPartialSolution);
				}
			}
		}
		
		return solutions;
	}

	private static class PartialSolution {
		private CellState[][] desk; 
		private int emptyCellCount;
		private int queenCount;
		private int size;
		private int maxCol=-1;
		
		private PartialSolution(int size) {
			this.size = size;
			desk = new CellState[size][size];
			for (int i = 0; i < desk.length; i++) {
				CellState[] row = desk[i];
				for (int j = 0; j < row.length; j++) {
					row[j] = CellState.FREE;
				}
			}
			emptyCellCount = size * size;
		}
		
		public int getEmptyCellCount() {
			return emptyCellCount;
		}
		
		public int getMaxCol() {
			return maxCol;
		}
		
		public CellState[][] getDesk() {
			return desk;
		}

		public boolean isFullSolution() {
			return queenCount == size;
		}
		
		public void putQueenAt(int r, int c) {
			maxCol = c;
			desk[r][c] = CellState.QUEEN;
			--emptyCellCount;
			++queenCount;
			
			for (int i = 0; i < size; i++) {
				if (i == c) continue;
				if (desk[r][i] != CellState.ATTACKED) {
					desk[r][i] = CellState.ATTACKED;
					--emptyCellCount;
				}
			}
			
			for (int i = 0; i < size; i++) {
				if (i == r) continue;
				if (desk[i][c] != CellState.ATTACKED) {
					desk[i][c] = CellState.ATTACKED;
					--emptyCellCount;
				}
			}
			
			for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
				if (desk[i][j] != CellState.ATTACKED) {
					desk[i][j] = CellState.ATTACKED;
					--emptyCellCount;
				}
			}
			
			for (int i = r + 1, j = c + 1; i < size && j < size; i++, j++) {
				if (desk[i][j] != CellState.ATTACKED) {
					desk[i][j] = CellState.ATTACKED;
					--emptyCellCount;
				}
			}
			
			for (int i = r + 1, j = c - 1; i < size && j >= 0; i++, j--) {
				if (desk[i][j] != CellState.ATTACKED) {
					desk[i][j] = CellState.ATTACKED;
					--emptyCellCount;
				}
			}
			
			for (int i = r - 1, j = c + 1; i >= 0 && j < size; i--, j++) {
				if (desk[i][j] != CellState.ATTACKED) {
					desk[i][j] = CellState.ATTACKED;
					--emptyCellCount;
				}
			}
		}

		public static PartialSolution createEmpty(int size) {
			return new PartialSolution(size);
		}
		
		public PartialSolution clone() {
			PartialSolution partialSolution = PartialSolution.createEmpty(size);
			partialSolution.queenCount = queenCount;
			partialSolution.emptyCellCount = emptyCellCount;
			for (int i = 0; i < desk.length; i++) {
				for (int j = 0; j < desk[i].length; j++) {
					partialSolution.desk[i][j] = desk[i][j];
				}
			}
			return partialSolution;
		}

		public boolean isDeadEnd() {
			return emptyCellCount == 0 && !isFullSolution();
		}

		@Override
		public String toString() {
			return toStringImpl(false);
		}

		private String toStringImpl(boolean isPrintAttacked) {
			StringBuilder sb = new StringBuilder();
			for (int k = 0; k < desk.length; k++) {
				sb.append(' ');
				sb.append('_');
			}
			sb.append(LINE_SEPARATOR);
			for (int i = 0; i < desk.length; i++) {
				sb.append('|');
				for (int j = 0; j < desk[i].length; j++) {
					switch(desk[i][j]) {
					case QUEEN:
						sb.append('*');
						break;
					case ATTACKED:
						sb.append(isPrintAttacked? 'x' : '_');
						break;
					case FREE:
						sb.append('_');
						break;
					}
					sb.append('|');
				}
				sb.append(LINE_SEPARATOR);
			}
			if (isPrintAttacked) {
				sb.append(String.format("emptyCellCount=%d%s", emptyCellCount, LINE_SEPARATOR));
			}
			
			return sb.toString();
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;

			for (int i = 0; i < desk.length; i++)
				for (int j = 0; j < desk[i].length; j++) {
					result = prime * result + (desk[i][j].ordinal()+1);
				}
			
			result = prime * result + emptyCellCount;
			result = prime * result + queenCount;
			result = prime * result + size;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			PartialSolution other = (PartialSolution) obj;
			if (size != other.size)
				return false;
			
			for (int i = 0; i < desk.length; i++) {
				for (int j = 0; j < desk[i].length; j++) {
					if (!desk[i][j].equals(other.desk[i][j])) {
						return false;
					}
				}
			}
			
			return true;
		}
	}
	
	private enum CellState {
		QUEEN,
		ATTACKED,
		FREE
	}
}
